package org.company.earth.arithmetic;

import java.util.List;

public class Sort<T> {
    
    public enum SortType {
        ASCEND,DESCEND
    }
    
    protected SortType sortType = SortType.ASCEND;
    
    protected void swap(List<T> arr,int i,int j) {
        T temp = arr.set(i, arr.get(j));
        arr.set(j, temp);
    }
    
    /**
     * 升序排列==》 origin<target
     * 降序排列==》origin>target
     * @param origin
     * @param target
     * @return
     */
    protected Boolean compare(T origin,T target) {
        Boolean flag = false;
        switch(sortType) {
        case ASCEND:
            flag = origin.hashCode() > target.hashCode(); 
            break;
        case DESCEND:
            flag = origin.hashCode() < target.hashCode();
            break;
        }
        return flag;
    }
    
    protected boolean gt(T priv,T next) {
        boolean flag = false;
        if(priv.hashCode() > next.hashCode()) {
            flag = true;
        }
        return flag;
    }
    
    protected boolean lt(T priv,T next) {
        boolean flag = false;
        if(priv.hashCode() < next.hashCode()) {
            flag = true;
        }
        return flag;
    }
    
    /**
     * 冒泡排序算法,找出最小数据
     * 时间复杂度 O(N^2)
     * 空间复杂度O(N)
     * 稳定算法
     * @param arr
     */
    public void bubble_sort(List<T> arr) {
        for(int i=0 ; i < arr.size() ; i++) {
            for(int j=0 ; j < arr.size() ; j++) {
                if(this.compare(arr.get(i),arr.get(j))) {
                    this.swap(arr, i, j);
                }
            }
        }
    }

    /**
     * 插入排序算法,
     * 假设前面n-1个数据已经排序完成，把第N个数插入到前面的有序队列
     * 时间复杂度O(N^2)
     * 空间复杂度O(N)
     * 稳定算法
     * @param arr
     */
    public void insert_sort(List<T> arr) {
        T key = null;
        int j = 0;
        for(int i=1 ; i < arr.size() ; i++) {
            key = arr.get(i);
            j = i - 1;
            while(j >= 0 && this.compare(key,arr.get(j))) {
                swap(arr,j,j+1);
                --j;
            }
        }
    }
    
    /**
     * 选择排序
     * 从未排序的队列中找出最小值，然后放到排序队列的末尾
     * 时间复杂度O(N^2)
     * 空间复杂度O(N)
     * 不稳定算法
     * @param arr
     */
    public void select_sort(List<T> arr) {
        int swap = 0;
        for(int i= 0 ; i <arr.size(); i++) {
            swap = i;
            for(int j = i + 1; j < arr.size() ; j++) {
                if(this.compare(arr.get(j), arr.get(swap))) {
                    swap = j;
                }
            }
            swap(arr,i,swap);
        }
    }
    
    public void print(List<T> arr) {
        for(T t : arr) {
            System.out.print(t + ",");
        }
        System.out.println();
    }
    
    public int partition(List<T> arr,int low,int high) {
        T val = arr.get(low);
        while(low < high) {
            while(low < high) {
                if(this.lt(arr.get(high),val)) {
                    this.swap(arr, low++, high);
                    break;
                }
                high--;
            }
            while(low < high) {
                if(this.gt(arr.get(low), val)) {
                    this.swap(arr, low, high--);
                    break;
                }
                low++;
            }
        }
        arr.set(low, val);
        print(arr);
        return low;
    }
    
    /**
     * 快速排序
     * 时间复杂度 O(nlogn) ~ O(n^2)
     * @param arr
     * @param low
     * @param high
     */
    public void quick_sort(List<T> arr,int low,int high) {
        if(low >= high) {
            return;
        }
        int privo = this.partition(arr,low,high);
        this.quick_sort(arr,low,privo-1);
        this.quick_sort(arr,privo+1,high);
    }
}
